<!DOCTYPE html>  
<html>
    <meta charset="utf-8" />  
    <title>二分搜索</title>  
<body>
    <h1>二分搜索</h1>
    <h2>
            选择数组的中间值
            如果选中值是待搜索值，算法执行完毕（值找到了）
            如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找
            如果待搜索值比选中值要大，则返回步骤1并在选种值右边的子数组中寻找
    </h2>
</body>
<script>  
    const arr = [1,4,5,8,9,1,2,6];

    Array.prototype.quickSort = function(){
        function quick(that){
            var len = that.length;
            if(len<=1){
                return that;
            }
            let middleNum = that[0];
            let right = [];
            let left = [];
            for(let i=1;i<len;i++){
                if(middleNum<that[i]){
                    right.push(that[i])
                }else{
                    left.push(that[i]);
                }
            }
            return [].concat(quick(left),[middleNum],quick(right));
        }
        return quick(this);
    }
    
    Array.prototype.binarySearch = function(item) {
        var ary = this.quickSort()
        let low = 0
        let mid = null
        let element = null
        let high = ary.length - 1
        while (low <= high){
            mid = Math.floor((low + high) / 2)
            element = ary[mid]
            console.log('element',element)
            if (element < item) {
                low = mid + 1
            } else if (element > item) {
                high = mid - 1
            } else {
                return mid
            }
        }
        return -1
    }
    console.log(arr.binarySearch(9))
</script>  
</html>